package 字符串.字符串排序;

import java.util.Arrays;

/**
 * @description:
 * @author: ywk
 * @date: 2021-08-24
 */
public class 低位优先的字符串排序 {
    public static class LSD{
        public static void sort(String[] a, int w) {
            int N = a.length;
            int R = 256;
            String[] aux = new String[N];
            for (int d = w - 1; d >= 0; d--) {
                int[] count = new int[R + 1];
                for (int i = 0; i < N; i++) {
                    //计算频率
                    count[a[i].charAt(d) + 1]++;
                }
                for (int r = 0; r < R; r++) {
                    //见频率转化为索引
                    count[r + 1] += count[r];
                }
                for (int i = 0; i < N; i++) {
                    //将元素分类
                    aux[count[a[i].charAt(d)]++] = a[i];
                }
                for (int i = 0; i < N; i++) {
                    a[i] = aux[i];
                }
            }
        }
    }

    public static void main(String[] args) {
        String[] sort = new String[]{"AEE0", "AB08", "AES0", "CEH8"};
        LSD.sort(sort, 4);
        System.out.println(Arrays.asList(sort));

    }
}
